package com.example.graph;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 * <p>
 * 示例 1：
 * <p>
 * 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
 * 输出：4
 * 解释：最长递增路径为[1, 2, 6, 9]。
 * <p>
 * 示例 2：
 * <p>
 * 输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
 * 输出：4
 * 解释：最长递增路径是[3, 4, 5, 6]。注意不允许在对角线方向上移动。
 * <p>
 * 示例 3：
 * <p>
 * 输入：matrix = [[1]]
 * 输出：1
 * <p>
 * 提示：
 * <p>
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 200
 * 0 <= matrix[i][j] <= 231 - 1
 */
public class Leetcode329_LongestIncreasingPath {
    public static void main(String[] args) {

        int[][] matrix = {
                {9, 9, 4},
                {6, 6, 8},
                {2, 1, 1}};

        System.out.println(new Solution().longestIncreasingPath(matrix));

    }

    static class Solution {
        private int[][] directs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 定义上下左右四个遍历方向
        private int rows;
        private int columns;


        public int longestIncreasingPath(int[][] matrix) {
//            return longestIncreasingPath1(matrix);
//            return longestIncreasingPath2(matrix);
            return longestIncreasingPath3(matrix);
        }

        /**
         * 解法一:暴力法
         * <p>
         * DFS逐个遍历求出矩阵的每个元素的最长递增路径长度
         * 然后返回结果中最大的递增路径长度即可
         *
         * @param matrix
         * @return
         */
        public int longestIncreasingPath1(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
                return 0;
            int res = 1;
            rows = matrix.length;
            columns = matrix[0].length;

            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    res = Math.max(dfsTraverse(matrix, i, j), res); // 每次更新最长递增路径长度
                }
            }
            return res;

        }

        /**
         * 解法二:DFS遍历优化
         * 暴力法有很多重复计算的情况
         * 将已经计算完毕的元素的最长递增路径长度记录下来，后面如果要用到直接取即可
         * 比如针对[[9,9,4],[6,6,8],[2,1,1]]
         * 当需要计算matrix[2][1](1)的最长递增路径长度时，按照从左到右从上到下的遍历方式matrix[2][0](2)的最长路径已经计算完毕
         * 此时只需要加上1-->2的路径长度即可
         * <p>
         * 优化思路:
         * 额外维护一个数组记录当前已经确定最长路径的节点及长度
         * 如果搜索到达的当前节点已经确定了最长路径的长度，那么直接返回该长度，无需继续扩展该节点
         *
         * @param matrix
         * @return
         */
        private int[][] longestPathLengths; // 记录从各个节点出发的最长路径的长度

        public int longestIncreasingPath2(int[][] matrix) { // 方法整体同法一
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
                return 0;
            int res = 1;
            rows = matrix.length;
            columns = matrix[0].length;
            longestPathLengths = new int[rows][columns];

            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    res = Math.max(dfsTraverse2(matrix, i, j), res); // 每次更新最长递增路径长度
                }
            }
            return res;
        }

        /**
         * 解法三:拓扑排序
         * 首先找到入度为 0 的节点
         * <p>
         * 然后删除这些节点的出边，再找出剩下节点中
         * 入度为0 的 节点，如此往复就可以完成拓扑排序
         *
         * @param matrix
         * @return
         */
        public int longestIncreasingPath3(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) return 0;
            rows = matrix.length;
            columns = matrix[0].length;
            int[][] indegrees = new int[rows][columns]; // 用于记录每个节点的入度

            // 初始化每个节点的入度
            for (int i = 0; i < rows; ++i)
                for (int j = 0; j < columns; ++j)
                    for (int[] dir : directs) {
                        int newRow = i + dir[0], newColumn = j + dir[1];
                        if (newRow >= 0 && newRow < rows &&
                                newColumn >= 0 && newColumn < columns &&
                                matrix[newRow][newColumn] < matrix[i][j])
                            ++indegrees[i][j];
                    }


            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < rows; ++i)
                for (int j = 0; j < columns; ++j) //将矩阵中所有初始的入度为0的节点加入队列
                    if (indegrees[i][j] == 0)
                        queue.offer(new int[]{i, j});

            int ans = 0;
            while (!queue.isEmpty()) {
                ++ans;
                int size = queue.size();
                for (int i = 0; i < size; ++i) {
                    int[] tpm = queue.poll();
                    int row = tpm[0], column = tpm[1];
                    for (int[] dir : directs) {
                        int newRow = row + dir[0], newColumn = column + dir[1];
                        if (newRow >= 0 && newRow < rows && newColumn >= 0 &&
                                newColumn < columns && matrix[newRow][newColumn] > matrix[row][column]) {
                            --indegrees[newRow][newColumn];

                            if (indegrees[newRow][newColumn] == 0)
                                queue.offer(new int[]{newRow, newColumn});
                        }
                    }
                }
            }

            return ans;
        }

        /**
         * dfs求出matrix[x][y]的最长递增路径
         *
         * @param matrix
         * @param row
         * @param column
         * @return
         */
        private int dfsTraverse(int[][] matrix, int row, int column) {
            int result = 1;
            // 四个方向判断是否比当前元素大，如果大递增路径就要增加(依次递归下去)
            for (int[] direct : directs) { // dfs递归求最大递增路径
                int newRow = row + direct[0], newColumn = column + direct[1];
                if (newRow >= 0 && newRow < rows && // 行要满足在矩阵范围内
                        newColumn >= 0 && newColumn < columns && // 列要满足在矩阵范围内
                        matrix[newRow][newColumn] > matrix[row][column]) { // 邻接元素要比当前元素大
                    result = Math.max(dfsTraverse(matrix, newRow, newColumn) + 1, result);
                }
            }
            return result;
        }

        private int dfsTraverse2(int[][] matrix, int row, int column) { // 优化版dfs
            // 如果已经计算过了，直接返回即可
            if (longestPathLengths[row][column] != 0)
                return longestPathLengths[row][column];

            longestPathLengths[row][column] = 1;
            // 四个方向判断是否比当前元素大，如果大递增路径就要增加(依次递归下去)
            for (int[] direct : directs) { // dfs递归求最大递增路径
                int newRow = row + direct[0], newColumn = column + direct[1];
                if (newRow >= 0 && newRow < rows && // 行要满足在矩阵范围内
                        newColumn >= 0 && newColumn < columns && // 列要满足在矩阵范围内
                        matrix[newRow][newColumn] > matrix[row][column]) { // 邻接元素要比当前元素大
                    longestPathLengths[row][column] = Math.max(dfsTraverse2(matrix, newRow, newColumn) + 1,
                            longestPathLengths[row][column]);
                }
            }
            return longestPathLengths[row][column];
        }


    }
}
